package codetop.microsoft.T207;

import java.util.*;

/**
 * @Author: 18362
 * @Create: 2022-08-13 17:30:13 星期六
 */
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new List[numCourses];
        int[] pre = new int[numCourses];
        for (int i=0; i<numCourses; ++i)
            graph[i] = new ArrayList<Integer>();
        for (int i=0; i<prerequisites.length; ++i) {
            int u = prerequisites[i][0], v = prerequisites[i][1];
            graph[v].add(u);
            pre[u]++;
        }
        Set<Integer> set = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0; i<numCourses; ++i) {
            if (pre[i] == 0)
                queue.offer(i);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i=0; i<size; ++i) {
                int u = queue.poll();
                for (int v : graph[u]) {
                    pre[v]--;
                    if (pre[v] == 0)
                        queue.offer(v);
                }
            }
        }
        for (int i=0; i<numCourses; ++i) {
            if (pre[i] > 0)
                return false;
        }
        return true;
    }
}